package algorithm;

import java.util.ArrayList;
import java.util.List;

public class leetcode_0039 {
    public static void main(String[] args) {
        int [] candidates={2,3,6,7};
        int target=7;
        System.out.println(combinationSum(candidates,target));
    }
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len=candidates.length;
        List<List<Integer>> list=new ArrayList<>();
        List<Integer> path=new ArrayList<>();
        dfs(target,list,0,len,candidates,path);
        return list;
    }
    public static void dfs(int target,List<List<Integer>> list,int begin,int len,int[]candidates,List<Integer> path){
        if(target<0){

            return;
        }
        else if(target==0){
            int len1=path.size();
            List<Integer>path1=new ArrayList<>(len1);
            for(int k=0;k<len1;++k){
                path1.add(path.get(k));
            }
            list.add(path1);
            return;
        }
        else{
            for(int i=begin;i<len;++i){
                path.add(candidates[i]);
                dfs(target-candidates[i],list,i,len,candidates,path);
                path.remove(path.size()-1);
            }
        }
    }
}
